Many computer systems provide for dynamic allocation of data objects. The performance of these systems relies on the ability to reclaim and re-use memory that has been dynamically allocated to objects after the objects are no longer being used by an executing program. In practice, an object is considered unused when no reference on a computer system refers to the object. When no reference refers to an object, the object is referred to as "dead". Garbage collection refers to the process of automatically reclaiming memory that is currently allocated to dead objects.
Garbage collection may be performed in cycles referred to as garbage collection cycles. During a garbage collection cycle, a set of operations are performed to identify the dead and live objects within a memory area at a particular point in time, and to reclaim memory allocated to the identified dead objects. Typically, during a garbage collection cycle, the objects that reside in the memory that is undergoing garbage collection may not be accessed by user processes (processes that are not involved in the garbage collection operation).
A garbage collection cycle is commenced when a garbage collection event is detected. Garbage collection events include, for example, an "insufficient memory" response during an attempt to allocate memory for a new object. A garbage collection event may simply be the lapse of a threshold period of time, thus causing garbage collection to be performed on a periodic basis.
One conventional method of garbage collection is known as the "tracing" approach. According to the tracing approach, a "trace" is performed during each garbage collection cycle. A trace is an operation performed to identify objects that are not dead (i.e. "live" objects). During a trace, live objects are identified by following direct and indirect references that exist in one or more areas of memory. An area of memory that contains references which directly or indirectly refer to live objects is referred to as a "root set". A base set is a set of root sets that are traced by a garbage collector to find all the live objects in the area of memory being managed by the garbage collector.
Any object not identified through a trace of the root sets in the base set is considered dead, and memory allocated to the object may be reclaimed. For example, assume that a call stack S is the only root set in the base set for a garbage collector that manages memory A. Assume also that object A, object B, and object C reside in memory A. A reference from call stack S refers to object A, and a reference within object A refers to object B. Object A is thus directly referenced by the reference in call stack S, and object B is indirectly referenced by the reference in call stack S. A trace through the call stack therefore identifies object A and object B, but not object C. Object C is therefore dead, and memory allocated to object C may be reclaimed.
The tracing approach poses several problems for computer systems that use large amounts of memory to store objects. Because execution of processes running on the computer system (e.g. real-time applications) are paused during garbage collection, and a trace accesses all the active objects, long delays in the execution of the processes may occur. Furthermore, accessing all the objects on a computer system violates the presumption of locality of reference that underlies virtual memory operating systems, and may result in excessive memory page thrashing.
One common approach used in conjunction with the tracing approach is the copying approach. Under the conventional "copying" approach, an area of memory is divided into semispaces. A semispace is an area of memory used to store objects which are garbage collected using the copying approach. One semispace is designated as the "to-space", and one is designated as the "from-space". Live objects are stored in the from-space, and newly created objects are allocated memory from the from-space.
During a garbage collection cycle, live objects identified through a trace are copied into the to-space. An object is copied into the to-space beginning at the memory location that immediately follows the memory area into which the previously copied object was copied. Because most objects in the from-space are dead (due to the short life span of the objects), the total memory allocated to the objects copied to the to-space from the from-space is typically much smaller than the amount that was allocated to all objects in the from-space. The difference represents reclaimed memory.
Because the moved objects now reside at new storage locations, all references referring to any object that was copied must be reset to refer to the new location of the copied object. Finally, the to-space is established as the current from-space, and the former from-space becomes the current to-space. New objects are allocated memory from the unoccupied portion of the current from-space (the semispace to which live objects have just been copied).
One advantage of the copying approach is that live objects are compacted into one end of the to-space, thereby reducing fragmentation. Another advantage is that the objects most likely to have longer life spans, i.e. the set of objects that are alive at the end of a garbage collection cycle, are clustered into fewer pages of memory. This results in greater data locality.
A disadvantage of the copying approach is that memory utilization is inefficient. Because the memory area managed by the garbage collector is divided into two semispaces, only one of which is used to store live objects, the greatest memory utilization that may be achieved is 50%. This inefficiency becomes more problematic for memory areas that are concurrently shared by a relatively greater number of processes.
FIG. 1, for example, shows a database system 101, which is used to illustrate problems associated with the conventional copying approach on computer systems with memory areas that are concurrently shared by a relatively large number of processes. Referring to FIG. 1, database system 101 receives calls from one or more clients 160. A call is a request to perform a task. A call may be, for example, a query in the form of an SQL statement, or a method invocation of a Java.TM. object or class residing on database system 101.
Before client 161 issues any calls to database server 101, a database session must be created for client 161. A database session is the establishment of a particular connection between a client and a database system through which a series a calls may be made. While the client remains connected in the database session, the client and the database session are referred to as being active.
When client 161 calls database server 101, one of server processes 110 is assigned to execute the call. At any given moment of time, a server process is assigned to execute the call of no more than one client. However, after a server process completes its execution of a call from one client, the server process may be assigned to respond to the call of another client. Thus, over a period of time, a server process may be assigned to execute the calls of multiple clients.
The number of calls requiring execution by a server process is typically less than the current number of active clients. Thus, database system 101 is typically configured to run less server processes than the maximum number of clients who may be active.
Database system 101 includes various memory areas used to store data used by server processes 110. These include call shared memory area 120, call global area 130, and session space 140. A shared memory area, such as shared memory area 120, is used to store data that may be shared concurrently by more than one process. For example, shared memory area may be used store the code for routines (e.g. byte code of Java classes) executed by multiple server processes 110.
A call global area, such as call global area 130, is used to store data that is bounded by the lifetime of a call. An example of such data is provided by the illustration that follows. Client 161 calls database system 101 to execute a first method of a first object. The invocation of the first method creates a first set of objects, and causes the invocation of a second method, which creates a second set of objects. After exiting the second and first invocation, the first and second set of objects are no longer alive (i.e. referenced). Objects, such as the first and second set of objects, that are only alive for the lifetime of a call may be stored in the call global area 130.
A session space, such as session space 140, is used to store static data. Static data, as used herein, refers to data associated with a user which is preserved for the duration of a series of calls. For example, static data includes data that is preserved between calls issued by a client during a single database session. Java class variables are an example of such static data.
The percentage of a memory area that can actually be used to store data largely depends on the memory management technique used to manage the memory area. The percentage of a memory area that can actually be used to store data is referred to as the "memory utilization rate". For example, at any given time, only 50% of a memory area managed using the "copying" garbage collection approach can be used to store live objects. The other 50% must be available for use as the "to-space" in the next garbage collection cycle. Thus, a memory area managed using the copying garbage collection approach has a memory utilization rate of 50%.
The memory utilization rates associated with the various memory areas used within a computer system have an effect on various operating characteristics of the system. For example, the maximum number of database sessions that can be concurrently active on database system 101 is affected by the memory utilization rate of session space 140, as illustrated in the following example.
Session Space: For purpose of explanation, the size of session space 140 is 1 megabyte ("mb"). A database session on average requires 10 kilobytes ("kb") of session space 140. In order to preserve objects between the calls for a given database session, on average 10 kb of session space 140 is exclusively apportioned to each active database session. If the memory utilization rate of session space 140 is 80%, then there may be a maximum of 80 concurrent active database sessions (1 mb/10 kb*0.8). If, however, the memory utilization rate of session space 140 is 50% (the best that can be achieved under the copying approach), then the maximum number of concurrent sessions is 50.
Call Global Area: As mentioned above, the lifetime of objects in call global area 130 is bounded by a call, while the lifetime of objects in session space 140 is bounded by a series of calls. The lifetime of objects stored in a memory area affects the impact of memory utilization for that memory area upon scalability, as illustrated in the following example.
For purposes of exposition, the size of call global area 130 is 1 mb. On average 10 kb of call global area 130 is apportioned to service a particular call for a database session. Because memory is only needed for the lifetime of the call, the apportionment lasts only for the duration of the call.
At any given moment, 25% of the database sessions have active calls that are being serviced. If the memory utilization rate is 80%, then there may be a maximum of 320 concurrent sessions (1 mb/0.25*10 kb *0.8). If, however, the memory utilization rate is 50%, then the maximum number of concurrent sessions is 200.
Shared Memory Area: Unlike session space 140, objects in shared memory area 120 may be shared concurrently by multiple clients. The number of database sessions that concurrently share data (i.e. one or more objects) stored in an area of shared memory area affects the impact of memory utilization of that shared memory area upon scalability.
For purposes of exposition, shared memory area 120 is 1 mb. On average two sessions concurrently share 10 kb portion of shared memory area 120. If the memory utilization rate is 80%, then there may be a maximum of 160 concurrent active sessions (1 mb/10 kb*0.8*2). If, however, the memory utilization rate is 50%, then the maximum number of concurrent active clients is 100.
As demonstrated above, in comparison to the call global area and shared memory area, reduced memory utilization of the session space costs more in terms of user scalability. It is therefore desirable to provide a "copying" garbage collection method with greater memory utilization, especially for memory areas where reduced memory utilization rates are more costly.